package datastructures;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeSet;

import algorithms.Algo;
import algorithms.Dic;

/**
 * @author Yuval Kesten
 *         <ul>
 *         My implementation of the Hash Tree Node with the relevant methods and
 *         fields for DIC
 *         </ul>
 */
public class DicHashTreeNode implements Comparable<DicHashTreeNode>, INode {

	public ItemSet set;
	public int depth;
	public HashMap<String, DicHashTreeNode> childrens;
	public HashSet<String> frequentChildrens;
	public DicHashTreeNode parent;
	public String keyAtPArent;
	boolean updatedParent;
	public long discoveryIndex;// Equals to iteration_number * basket_index
	public long lastEncounterdIndex = 0;
	private Set<String> prunedChildrens;

	public DicHashTreeNode(int _depth, long _discIndex) {
		childrens = new HashMap<String, DicHashTreeNode>(22);
		depth = _depth;
		discoveryIndex = _discIndex;
		updatedParent = false;
		frequentChildrens = new HashSet<String>(22);
		prunedChildrens = new HashSet<String>(22);
		keyAtPArent = "";
	}

	public DicHashTreeNode(int depth, long basketIndex, String word, DicHashTreeNode root, int iterNum,
			int numOfBaskets, double support) {
		this(depth, basketIndex);
		set = new ItemSet();
		set.addItem(word);
		parent = root;
		keyAtPArent = word;
		root.put(word, this);
		encounterNode(basketIndex, numOfBaskets, 0, iterNum);
	}

	public boolean pruneAtDepth(Dic dicAlgo, double support, int numOfBaskets, int pruneDepth, long basketIndex) {

		// A leaf
		if (childrens == null || childrens.isEmpty())
			return false;

		if (basketIndex <= discoveryIndex + numOfBaskets) {
			return true;
		}

		boolean alive = false;// There are still live itemsets of size
								// $pruneDepth

		Iterator<String> iter1 = childrens.keySet().iterator();
		DicHashTreeNode node;
		String key;

		// Prune or find the correct depth
		while (iter1.hasNext()) {
			key = iter1.next();
			node = childrens.get(key);
			try {
				if (node.pruneCondition(dicAlgo.getSupportAsInt(support, node.discoveryIndex), numOfBaskets,
						basketIndex)) {
					prunedChildrens.add(node.keyAtPArent);
				} else
					alive = true;
			} catch (Exception e) {
				System.out.println(e.getLocalizedMessage());
			}
		}
		// Remove all the deleted ones
		for (String prunedChild : prunedChildrens) {
			childrens.remove(prunedChild);
		}
		if (childrens != null) {
			for (Entry<String, DicHashTreeNode> entry : childrens.entrySet()) {
				if (entry.getValue().pruneAtDepth(dicAlgo, support, numOfBaskets, pruneDepth, basketIndex))
					alive = true;
			}
		}

		return alive;
	}

	public boolean discoverTillDepth(Dic dicAlgo, double support, int numOfBaskets, int discoverDepth, long basketIndex) {

		// A leaf
		if (childrens == null || childrens.isEmpty())
			return false;

		if (depth > 0 && !isFrequent(dicAlgo.getSupportAsInt(support, this.discoveryIndex))) {
			return false;
		}

		if (depth > discoverDepth) {
			return false;
		}

		ItemSet newIS;
		boolean foundNewItemset = false;

		// Discover or find the correct depth
		{
			TreeSet<String> sortedChildrensKeys = new TreeSet<String>();
			for (String child : frequentChildrens) {
				sortedChildrensKeys.add(child);
			}

			Iterator<String> ascIter = sortedChildrensKeys.iterator();
			Iterator<String> desIter;
			String key1, key2;
			DicHashTreeNode node1, node2;
			DicHashTreeNode newNode;
			boolean foundNode1 = false;
			while (ascIter.hasNext()) {
				key1 = ascIter.next();
				node1 = childrens.get(key1);
				if (node1 == null || !node1.isFrequent(dicAlgo.getSupportAsInt(support, node1.discoveryIndex)))
					continue;
				desIter = sortedChildrensKeys.descendingIterator();

				while (desIter.hasNext()) {
					key2 = desIter.next();

					if (key2.equals(key1)) {
						break;
					}

					// Maybe node2 was already a son of node but it was pruned
					if (node1.prunedChildrens.contains(key2)) {
						continue;
					}

					// Maybe this was discovered before
					if (node1.childrens.containsKey(key2))
						continue;

					node2 = childrens.get(key2);
					if (node2 == null || !node2.isFrequent(dicAlgo.getSupportAsInt(support, node2.discoveryIndex)))
						continue;

					foundNewItemset = true;
					Algo.incStats(node1.depth + 1);

					// Two good candidates - merge them!
					newIS = new ItemSet();
					for (String item : node1.set) {
						newIS.addItem(item);
					}
					newIS.addItem(key2);// node2.set.getLast()==key2
					newNode = new DicHashTreeNode(node1.depth + 1, basketIndex + 1);
					newIS.counter = 0;
					newNode.set = newIS;
					newNode.parent = node1;
					newNode.keyAtPArent = key2;
					node1.put(key2, newNode);
				}
			}
		}
		if (depth < discoverDepth - 1) {
			for (Entry<String, DicHashTreeNode> entry : childrens.entrySet()) {
				if (entry.getValue().discoverTillDepth(dicAlgo, support, numOfBaskets, discoverDepth, basketIndex)) {
					foundNewItemset = true;
				}
			}
		}
		return foundNewItemset;
	}

	/***
	 * Check if this subtree is ready for pruning
	 * 
	 * @return true iff we should prune this sub tree
	 */
	boolean pruneCondition(int absSupport, int numOfBaskets, long basketIndex) {
		return !isFrequent(absSupport) && basketIndex > discoveryIndex + numOfBaskets;
	}

	boolean isFrequent(int absSupport) {
		return set.counter > absSupport;
	}

	public void put(String key, DicHashTreeNode child) {
		childrens.put(key, child);
	}

	public boolean conatins(String key) {
		return childrens.containsKey(key);
	}

	/***
	 * We count a node only if this is the first time we count it for a given
	 * basket That means that we will conut it only for baskets which appears in
	 * the next <code>numOfBaskets</code> from its discovery
	 * 
	 * @param basketIndex
	 * @param iterationNumber
	 * @param numOfBaskets
	 * @param iterNum
	 */
	public void encounterNode(long basketIndex, int numOfBaskets, int support, int iterNum) {

		// During the first iteration we count everything
		if (iterNum > 1) {
			if (basketIndex >= discoveryIndex + numOfBaskets)
				return;
		}

		lastEncounterdIndex = basketIndex;

		set.counter++;
		if (!updatedParent && set.counter > support) {
			updatedParent = true;
			if (parent == null || parent.frequentChildrens == null)
				return;
			parent.frequentChildrens.add(keyAtPArent);
		}
	}

	@Override
	public int getNumOfChildrens() {
		return childrens.size();
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((keyAtPArent == null) ? 0 : keyAtPArent.hashCode());
		result = prime * result + ((parent == null) ? 0 : parent.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		DicHashTreeNode other = (DicHashTreeNode) obj;
		if (keyAtPArent == null) {
			if (other.keyAtPArent != null)
				return false;
		} else if (!keyAtPArent.equals(other.keyAtPArent))
			return false;
		if (parent == null) {
			if (other.parent != null)
				return false;
		} else if (!parent.equals(other.parent))
			return false;
		return true;
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		if (set != null)
			sb.append(set.toString());
		if (childrens != null) {
			for (String key : childrens.keySet()) {
				sb.append(childrens.get(key).toString());
			}
		}
		return sb.toString();
	}

	public String toString(int support) {
		if (set != null && set.counter <= support)
			return "";
		if (set != null && set.counter == 0)
			return "";
		StringBuilder sb = new StringBuilder();
		if (set != null)
			sb.append(set.toString());
		if (childrens != null) {
			for (String key : childrens.keySet()) {
				sb.append(childrens.get(key).toString(support));
			}
		}
		return sb.toString();
	}

	@Override
	public int compareTo(DicHashTreeNode o) {
		if (this.equals(o)) {
			return 0;
		}

		return this.keyAtPArent.compareTo(o.keyAtPArent);
	}
}